package cn.dapeng.array;

import cn.dapeng.utils.BuilderArray;

/**
 * @BelongProject study
 * @BelongPackage cn.dapeng.array
 * @Description 前缀和
 * @ClassName PreSum
 * @Author xupenghong
 * @Date 2024/9/5 14:06
 * @Version 1.0.0
 * <p>
 * <p>
 * 给定一个数组， 求从第l个数到第r个数之间连续的数的和
 */
public class PreSum {

    /**
     * 给定一个数组，算出前缀和数组
     *
     * @param array
     * @return
     */
    public static int[] preSum(int[] array) {
        if (array == null) {
            return null;
        }
        if (array.length < 2) {
            return array;
        }
        int size = array.length;
        int[] preNumArray = new int[size];

        preNumArray[0] = array[0];
        for (int i = 1; i < size; i++) {
            preNumArray[i] = preNumArray[i - 1] + array[i];
        }
        return preNumArray;
    }

    /**
     * 求从l开始到r位置，每个数相加的和
     *
     * @param array : 前缀和数组
     * @param l     :
     * @param r     :
     * @return
     */
    public static int getRangeSum(int[] array, int l, int r) {
        if (l > r) {
            return -1;
        }
        if (r > array.length - 1) {
            r = array.length - 1;
        }
        return array[r] - array[l - 1];
    }

    public static int getRangeSum2(int[] array, int l, int r) {
        if (l > r) {
            return -1;
        }
        int size = array.length;

        if (r > size - 1) {
            r = size - 1;
        }

        int[][] preSum = new int[size][size];

        for (int row = 0; row < size; row++) {
            for (int column = 0; column < size; column++) {
                if (column == row) {
                    preSum[row][column] = array[column];
                } else if (column > row) {
                    preSum[row][column] = preSum[row][column - 1] + array[column];
                }
            }
        }

        return preSum[l][r];
    }

    public static void main(String[] args) {
        int testTime = 100000;
        int l = 1, r = 100;
        for (int i = 0; i < testTime; i++) {
            int[] array = BuilderArray.builderArray(100, 20);
            int[] preNumArray = preSum(array);

            if (getRangeSum(preNumArray, l, r) != getRangeSum2(array, l, r)) {
                System.out.println("Oops");
                break;
            }
        }
    }
}
